#include <iostream>
#include <string>
#include <stack>
#define MAX_VARIABLE_NUM 26
#define STACK_INIT_SIZE 128
#define STACK_INCREMENT 32
using namespace std;

typedef struct Node
{
    char data;
    BTNode *lchild;
    BTNode *rchild;
} BTNode, BinaryTree;

typedef void *visit(Node);

typedef struct Stack
{
    Node *base;
    Node *top;
    int stacksize;
} SqStack;

void Exit(string message)
{
    cout << "ERROR:" << message << endl;
    exit(1);
}

//初始化栈
void InitStack(Stack &S)
{
    S.base = (char *)malloc(STACK_INIT_SIZE * sizeof(char));
    if (!S.base)
        Exit("Memory Deficiency");
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
}

//弹出并返回栈顶元素
template <class T>
bool Pop(Stack &S, T &e)
{
    if (S.top == S.base)
        return 0;
    e = *--S.top;
    return 1;
}

//入栈
void Push(Stack &S, char e)
{
    if (S.top - S.base >= S.stacksize)
    {
        S.base = (char *)realloc(S.base, (S.stacksize + STACK_INCREMENT) * sizeof(char));
        if (!S.base)
            Exit("Stack Overflow");
        S.top = S.base + S.stacksize;
        S.stacksize += STACK_INCREMENT;
    }
    *S.top++ = e;
}

//判断栈是否空，空的话返回1， 否则返回0
bool IsStackEmpty(Stack &S)
{
    if (S.base == S.top)
    {
        return 1;
    }
    return 0;
}

void InitBiTree(BinaryTree &T)
{
    T.parent = NULL;
    T.lchild = NULL;
    T.rchild = NULL;
}

void DestroyBiTree(BinaryTree *&T)
{
    if (T)
    {
        DestroyBiTree(T->lchild);
        DestroyBiTree(T->rchild);
        delete T;
    }
    T = NULL;
}

void InitNode(Node &e)
{
    e.parent = &e;
    e.lchild = NULL;
    e.rchild = NULL;
}

bool BiTreeEmpty(BinaryTree &T)
{
    return T.lchild == NULL && T.rchild == NULL;
}

Node *LeftChild(Node &e)
{
    return e.lchild;
}

Node *RightChild(Node &e)
{
    return e.rchild;
}

Node *Parent(Node &e)
{
    return e.parent;
}

Node *LeftSibling(Node &e)
{
    if (e.parent == NULL)
    {
        return NULL;
    }
    return e.parent->lchild;
}
Node *RightSibling(BinaryTree &T, Node &e)
{
    if (e.parent == NULL)
    {
        return NULL;
    }
    return e.parent->rchild;
}
void *InsertChild(Node &p, bool LR, BinaryTree &C)
{
    if (LR)
    {
        p.lchild = &C;
    }
    else
    {
        p.rchild = &C;
    }
    C.parent = &p;
}
void *DeleteChild(Node &p, bool LR)
{
    if (LR)
    {
        DestroyBiTree(p.lchild);
        p.lchild = NULL;
    }
    else
    {
        DestroyBiTree(p.rchild);
        p.rchild = NULL;
    }
}
void PreOrderTraverse(BinaryTree &T, visit v)
{
    PreOrderTraverse(*T.lchild, v);
    v(T);
    PreOrderTraverse(*T.rchild, v);
}
void InOrderTraverse(BinaryTree &T, visit v)
{
    InOrderTraverse(*T.lchild, v);
    v(T);
    InOrderTraverse(*T.rchild, v);
}
void PostOrderTraverse(BinaryTree &T, visit v)
{
    PostOrderTraverse(*T.rchild, v);
    PostOrderTraverse(*T.lchild, v);
    v(T);
}

bool JudgeSimbol(char &c)
{
    switch (c)
    {
    case '&':
    case '~':
    case '+':
    case '(':
    case ')':
        return true;
    default:
        return false;
    }
}

char Precede(char &t1, char &t2)
{
    char f;
    switch (t2)
    {
    case '+':
        if (t1 == '(')
            f = '<';
        else
            f = '>';
        break;
    case '*':
        if (t1 == '*' || t1 == ')')
            f = '>';
        else
            f = '<';
        break;
    case '~':
        if (t1 == '*' || t1 == '~' || t1 == ')')
            f = '>';
        else
            f = '<';
        break;
    case '(':
        f = '<';
        break;
    case ')':
        if (t1 == '(')
            f = '=';
        else
            f = '>';
        break;
    case '=':
        f = '>';
    }
    return f;
}

bool CreateBinaryExpTree(BinaryTree *&T, char ch[])
{
    SqStack OPND, OPTR;
    InitStack(OPND);
    InitStack(OPTR);
    BTNode *p, *q, *s;
    int i = 0, m;
    char theta;
    while (!OPTR.empty() || ch[i] != '=')
    {
        if (JudgeSimbol(ch[i]))
        {
            if (ch[i] == '+' && (i == 0 || ch[i - 1] == '('))
            {
                // 处理单目运算符
                p = new Node;
                p->data = 0;
                p->lchild = p->rchild = NULL;
                OPND.push(*p);
            }
            if (OPTR.empty())
            {
                q = new Node;
                q->data = ch[i];
                q->lchild = q->rchild = NULL;
                OPTR.push(*q);
                i++;
            }
            else if (!OPTR.empty())
            {
                theta = OPTR.top().data;
                switch (Precede(theta, ch[i]))
                {
                case '<':
                    q = new Node;
                    q->data = ch[i];
                    q->lchild = q->rchild = NULL;
                    OPTR.push(*q);
                    i++;
                    break;
                case '=':
                    OPTR.pop();
                    i++;
                    break;
                case '>':
                    t = OPTR.top();
                    OPTR.pop();
                    if(OPND.empty())
                    {
                        return false;
                    }

                }
            }
        }
    }
}